{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Get Maximum in Generated Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaximumGenerated"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #获取生成数组中的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> 。按下述规则生成一个长度为 <code>n + 1</code> 的数组 <code>nums</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums[0] = 0</code></li>\n",
    "\t<li><code>nums[1] = 1</code></li>\n",
    "\t<li>当 <code>2 <= 2 * i <= n</code> 时，<code>nums[2 * i] = nums[i]</code></li>\n",
    "\t<li>当 <code>2 <= 2 * i + 1 <= n</code> 时，<code>nums[2 * i + 1] = nums[i] + nums[i + 1]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回生成数组 <code>nums</code> 中的 <strong>最大</strong> 值。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>根据规则：\n",
    "  nums[0] = 0\n",
    "  nums[1] = 1\n",
    "  nums[(1 * 2) = 2] = nums[1] = 1\n",
    "  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2\n",
    "  nums[(2 * 2) = 4] = nums[2] = 1\n",
    "  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3\n",
    "  nums[(3 * 2) = 6] = nums[3] = 2\n",
    "  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3\n",
    "因此，nums = [0,1,1,2,1,3,2,3]，最大值 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= n <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [get-maximum-in-generated-array](https://leetcode.cn/problems/get-maximum-in-generated-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [get-maximum-in-generated-array](https://leetcode.cn/problems/get-maximum-in-generated-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7', '2', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        num = [0] * (n + 1)\n",
    "        num[1] = 1\n",
    "        i = 2\n",
    "        for i in range(2 , n + 1):\n",
    "            if i % 2 == 0:\n",
    "                num[i] = num[i // 2]\n",
    "            else:\n",
    "                num[i] = num[i // 2] + num[i - (i // 2)]\n",
    "        return max(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        return max(self.res(n), self.getMaximumGenerated(n-1)) if n else 0\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def res(self, n):\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        return self.res(n//2) if not n % 2 else self.res(n//2) + self.res(n//2+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            nums[i] = nums[i // 2] + i % 2 * nums[i // 2 + 1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        nums = [0]*(n+1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "          nums[i]=nums[i//2]+i%2*nums[i//2+1]\n",
    "        return max(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        nums=[0]+[1]*n\n",
    "        if n>=2:\n",
    "            for i in range(2,n+1):\n",
    "                if i%2==1:\n",
    "                    nums[i]=nums[i//2]+nums[i//2+1]\n",
    "                else:\n",
    "                    nums[i]=nums[i//2]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        nums=[0  for i in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            if i == 0:\n",
    "                nums[i]=0\n",
    "            elif i == 1:\n",
    "                nums[i]=1\n",
    "            elif i%2==0:\n",
    "                nums[i]=nums[int(i/2)]\n",
    "            else:\n",
    "                nums[i]=nums[int(i/2)]+nums[int(i/2)+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[1] = 1        \n",
    "        for i in range(2, n + 1):\n",
    "            if i % 2 == 0:\n",
    "                nums[i] = nums[i // 2]\n",
    "            else:\n",
    "                nums[i] = nums[(i - 1) // 2] + nums[(i - 1) // 2 + 1]\n",
    "        return max(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        nums=[0]*(n+1)\n",
    "        nums[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            nums[i]=nums[i//2]+(i%2)*nums[i//2+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            nums[i] = nums[i // 2] + i % 2 * nums[i // 2 + 1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "        nums = [0]*(n+1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            if i % 2 == 0:\n",
    "                nums[i] = nums[i//2]\n",
    "            else:\n",
    "                nums[i] = nums[i//2] + nums[i//2+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        nums=[[0] for _ in range(n+1)]\n",
    "        if n==0:\n",
    "            return 0\n",
    "        elif n==1:\n",
    "            return 1\n",
    "        else:\n",
    "            nums[0]=0\n",
    "            nums[1]=1\n",
    "            for i in range(2,n+1):\n",
    "                if i%2==0:\n",
    "                    nums[i]=nums[i//2]\n",
    "                else:\n",
    "                    nums[i]=nums[i//2]+nums[i//2+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        nums = [0] * (n+1)\n",
    "        nums[1] = 1\n",
    "        max_nums = 0\n",
    "        for i in range(2,n+1):\n",
    "            res = int(i/2)\n",
    "            nums[i] = nums[res] + (i % 2) * nums[res+1]\n",
    "            max_nums = max(max_nums,nums[i])\n",
    "        return max_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        nums=list(range(0,n+2))\n",
    "        for i in range(1,n//2+1):\n",
    "            nums[2*i]=nums[i]\n",
    "            nums[2*i+1]=nums[i]+nums[i+1]\n",
    "        return max(nums[0:(n+1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        # if not n:\n",
    "        #     return = [0] * (n+1)\n",
    "        # nums = [0] * (n+1)\n",
    "        # nums[1] = 1\n",
    "        # for i in range(2 , n+1 , 2):\n",
    "        #     nums[i] = nums[i // 2]\n",
    "        #     if i < n:\n",
    "        #         nums[i+1] = nums[i//2] + nums[i//2 + 1]\n",
    "        # return max(nums)\n",
    "\n",
    "        if n < 2:\n",
    "            return n\n",
    "        \n",
    "        nums = [0] * (n+1)\n",
    "        nums[1] = 1\n",
    "        max_val = 1\n",
    "        # 循环的区间\n",
    "        for i in range(2 , n+1):\n",
    "            if i % 2 == 0:\n",
    "                nums[i] = nums[i // 2]\n",
    "            else:\n",
    "                nums[i] = nums[i // 2] + nums[i // 2 + 1]\n",
    "            max_val = max(max_val , nums[i])\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n + 1) \n",
    "        nums[0] = 0\n",
    "        nums[1] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            if 2 <= 2 * i <= n:\n",
    "                nums[2 * i] = nums[i]\n",
    "            if 2 <= 2 * i + 1 <= n:\n",
    "                nums[2 * i + 1] = nums[i] + nums[i+1]\n",
    "        \n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        nums = [0,1]\n",
    "        if n % 2 == 0:\n",
    "            i = 1\n",
    "            while i <= n/2:\n",
    "                nums.append(nums[i])\n",
    "                if i < n/2:\n",
    "                    nums.append( nums[i] + nums[i + 1])  \n",
    "                i += 1\n",
    "        else:\n",
    "            i = 1\n",
    "            while 2 * i + 1 <= n:\n",
    "                nums.append(nums[i])\n",
    "                nums.append( nums[i] + nums[i + 1])\n",
    "                \n",
    "                i += 1\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        return max(nums)\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        l = [0,1]\n",
    "        for i in range(2, n+1):\n",
    "            if i & 1:\n",
    "                l.append(l[i >> 1] + l[i // 2 + 1])\n",
    "            else:\n",
    "                l.append(l[i >> 1])\n",
    "        return max(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "\n",
    "        nums = [0] * (n+1)\n",
    "        nums[1] = 1\n",
    "        max_val = 1\n",
    "        for i in range(2, n+1):\n",
    "            if i%2 == 0:\n",
    "                nums[i] = nums[i//2]\n",
    "            else:\n",
    "                nums[i] = nums[i//2] + nums[i//2+1]\n",
    "            max_val = max(max_val, nums[i])\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[0] = 0\n",
    "        nums[1] = 1\n",
    "        for i in range(1,n):\n",
    "            if (2 * i > n) or (2 * i + 1 > n):\n",
    "                break\n",
    "            else:\n",
    "                nums[2 * i] = nums[i]\n",
    "                nums[2 * i + 1] = nums[i] + nums[i + 1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        num = [0] * (n+1)\n",
    "        num[1] = 1\n",
    "        res = 1\n",
    "        for i in range(2, n+1):\n",
    "            if i % 2 == 0:\n",
    "                num[i] = num[i//2]\n",
    "            else:\n",
    "                num[i] = num[i//2] + num[i//2+1]\n",
    "            res = max(res, num[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        nums = [0,1]\n",
    "        if n==0: return 0\n",
    "        if n==1: return 1\n",
    "        for i in range(2,n+1):\n",
    "            nums.append(int(0))\n",
    "            if i%2==0: \n",
    "                nums[i] = nums[int(i/2)]\n",
    "            else: nums[i] = nums[int((i-1)/2)] + nums[int((i-1)/2+1)] \n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        nums=[0]*(n+1)\n",
    "        nums[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            if i%2==0:\n",
    "                nums[i]=nums[i//2]\n",
    "            else:\n",
    "                nums[i]=nums[(i-1)//2]+nums[(i-1)//2+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n + 1):\n",
    "            if i % 2 == 0:\n",
    "                dp[i] = dp[i // 2]\n",
    "            else:\n",
    "                dp[i] = dp[i//2] + dp[i//2 + 1]\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        N=220\n",
    "        nums=[0 for _ in range(N)]\n",
    "        nums[1]=1\n",
    "        \n",
    "        for i in range(1,101):\n",
    "            if i>=1 and i*2<=n:\n",
    "                nums[2*i]=max(nums[2*i],nums[i])\n",
    "            if 2*i+1>=2 and 2*i+1<=n:\n",
    "                nums[2*i+1]=max(nums[2*i+1],nums[i]+nums[i+1])\n",
    "        return max(nums[:n+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [0 for i in range(n+1)]\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        for i in range(n+1):\n",
    "            if 2*i >=2 and 2*i <= n:\n",
    "                dp[2*i] = dp[i]\n",
    "            if (2*i+1) >=2 and (2*i+1) <=n:\n",
    "                dp[(2*i+1)] = dp[i] + dp[i+1]\n",
    "            \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n<=2:\n",
    "            return 1\n",
    "        res=[0]*(n+1)\n",
    "        res[1]=1\n",
    "        i=2\n",
    "        val=1\n",
    "        while i<=n:\n",
    "            #如果n为奇数\n",
    "            if i%2==1:\n",
    "                res[i]=res[(i-1)//2]+res[(i-1)//2+1]\n",
    "            else:\n",
    "                res[i]=res[i//2]\n",
    "            if res[i]>val:\n",
    "                val=res[i]\n",
    "            i+=1\n",
    "        return val\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n+1)\n",
    "        nums[1] = 1\n",
    "        for i in range(n):\n",
    "            if 2 * i <= n:\n",
    "                nums[2*i] = nums[i]\n",
    "            if 2 * i + 1 <= n:\n",
    "                nums[2*i+1] = nums[i] + nums[i+1]\n",
    "        return max(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        num = [0,1]\n",
    "        if n <2:return num[n]\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            num.append(num[i//2]) if i%2==0 else num.append(num[i//2]+num[i//2+1])\n",
    "        return max(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        h = [0, 1]\n",
    "        if n>=2:\n",
    "            for i in range(2, n + 1):\n",
    "                if i % 2 == 0:\n",
    "                    h.append(h[i // 2])\n",
    "                else:\n",
    "                    h.append(h[i//2] + h[i - (i//2)])\n",
    "            return max(h)\n",
    "        else:\n",
    "            return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        h = [0, 1]\n",
    "        if n>=2:\n",
    "            for i in range(2, n + 1):\n",
    "                if i % 2 == 0:\n",
    "                    h.append(h[i // 2])\n",
    "                else:\n",
    "                    h.append(h[i//2] + h[i - (i//2)])\n",
    "            return max(h)\n",
    "        else:\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def getvalue(n):\n",
    "    if n== 0 :\n",
    "        return 0\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    if n % 2 == 0:\n",
    "        return getvalue(n//2)\n",
    "    return getvalue(n//2)+getvalue(n//2+1)\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(n+1):\n",
    "            res = max(res,getvalue(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            nums[i] = nums[i // 2] + i % 2 * nums[i // 2 + 1]\n",
    "        return max(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        # nums[0] = 0\n",
    "        # nums[1] = 1\n",
    "        # 当2 <= 2 * i <= n时，nums[2 * i] = nums[i]\n",
    "        # 当2 <= 2 * i + 1 <= n时，nums[2 * i + 1] = nums[i] + nums[i + 1]\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        nums = [0 for i in range(n + 1)]\n",
    "        nums[0] = 0\n",
    "        nums[1] = 1\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            if 2 <= 2 * i <= n:\n",
    "                nums[2 * i] = nums[i]\n",
    "            if 2 <= 2 * i + 1 <= n:\n",
    "                nums[2 * i + 1] = nums[i] + nums[i + 1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        nums = [0] * (n+1)\n",
    "        nums[1] = 1\n",
    "        max_nums = 0\n",
    "        for i in range(2,n+1):\n",
    "            nums[i] = nums[int(i/2)] + (i % 2) * nums[int(i/2)+1]\n",
    "            max_nums = max(max_nums,nums[i])\n",
    "        return max_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0:return 0\n",
    "        if n==1:return 1\n",
    "        nn=[x for x in range(n+1)]\n",
    "        for i in range(2,n+1):\n",
    "            if i%2==0:nn[i]=nn[int(i/2)]\n",
    "            if i%2==1:nn[i]=nn[int((i-1)/2)]+nn[int((i-1)/2+1)]\n",
    "        print(nn)\n",
    "        return max(nn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        nums=[0]*(n+1)\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums[0] = 0\n",
    "        nums[1] = 1\n",
    "        for i in range(0,n+2):\n",
    "            if 2*i>=2 and 2*i<=n:\n",
    "                nums[2*i] = nums[i]\n",
    "            if 2*i+1>=2 and 2*i+1<=n:\n",
    "                nums[2*i+1] = nums[i]+nums[i+1]\n",
    "        \n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n+1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            nums[i] = nums[i // 2] + i % 2* nums[i // 2 + 1]\n",
    "        return max(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            nums[i] = nums[i // 2] + i % 2 * nums[i // 2 + 1]\n",
    "        return max(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[1] = 1\n",
    "        for i in range(1, n+1):\n",
    "            if 2 <= 2 * i <= n:\n",
    "                nums[2 * i] = nums[i]\n",
    "            if 2 <= 2 * i + 1 <= n:\n",
    "                nums[2 * i + 1] = nums[i] + nums[i+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0 : return 0\n",
    "        nums = [0]*(n+1)\n",
    "        nums[0] = 0\n",
    "        nums[1] = 1\n",
    "        for i in range(1,n+1):\n",
    "            if 2 * i <= n : nums[2 * i] = nums[i]\n",
    "            if 2 * i +1 <= n : nums[2 * i +1] = nums[i] + nums[i + 1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        nums=[0]*(n+1)\n",
    "        nums[1]=1\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if i%2==0:\n",
    "                nums[i]=nums[i//2]\n",
    "            else:\n",
    "                nums[i]=nums[i//2]+nums[i//2+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            if i % 2 == 0:\n",
    "                dp[i] = dp[i//2]\n",
    "            else:\n",
    "                dp[i] = dp[i//2] + dp[i//2 + 1]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        maxval = 0\n",
    "        for i in range(n + 1):\n",
    "            if i % 2 == 0:\n",
    "                dp[i] = dp[i // 2]\n",
    "            else:\n",
    "                dp[i] = dp[i // 2] + dp[i // 2 + 1]\n",
    "            if dp[i] > maxval:\n",
    "                maxval = dp[i]\n",
    "        return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        res = 0\n",
    "        temp = [0 for _ in range(n+1)]\n",
    "        temp[0] = 0\n",
    "        if n<2:\n",
    "            return n\n",
    "        temp[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            if i%2 == 0:\n",
    "                temp[i] = temp[i//2]\n",
    "            else:\n",
    "                temp[i] = temp[(i-1)//2]+temp[(i-1)//2+1]\n",
    "        print(temp)\n",
    "        return max(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        res = [0, 1]+[0]*(n-1)\n",
    "        for i in range(2, n+1):\n",
    "            if i % 2 == 0:\n",
    "                res[i] = res[i//2]\n",
    "            else:\n",
    "                res[i] =  res[(i-1)//2]+res[(i-1)//2+1]\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        #思路：比较直接，直接计算每个i的值，并求出最大值\n",
    "        nums = [0] * (n+1)\n",
    "        if n == 0: return 0\n",
    "        nums[1] = 1 \n",
    "        for i in range(1, n//2 + 1):\n",
    "            nums[2*i] = nums[i]\n",
    "            if (2*i + 1) <= n:\n",
    "                nums[2*i + 1] = nums[i] + nums[i+1]\n",
    "        return max(nums)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        nums=[0]*(n+1) #创建一个长度为n+1的列表，其中每个元素都是0\n",
    "        nums[1]=1\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if i%2==0: #若整数i能被2整除\n",
    "                nums[i]=nums[i//2]\n",
    "            else:  #整数i不能被2整除\n",
    "                nums[i]=nums[i//2]+nums[i//2+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n<2:\n",
    "            return n\n",
    "        a=[0]*(n+1)\n",
    "        a[1]=1\n",
    "        r=0\n",
    "        for i in range(2,n+1):\n",
    "            if i%2==0:\n",
    "                a[i]=a[i//2]\n",
    "            else:\n",
    "                a[i]=a[i//2]+a[i//2+1]\n",
    "            if a[i]>r:\n",
    "                r=a[i]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        nums=[0]*(n+1)\n",
    "        nums[0]=0\n",
    "        nums[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            if i%2==0:\n",
    "                nums[i]=nums[i//2]\n",
    "            elif i%2==1:\n",
    "                nums[i]=nums[(i-1)//2]+nums[(i-1)//2+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            nums[i] = nums[i // 2] + i % 2 * nums[i // 2 + 1]\n",
    "        return max(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n <= 1: return n\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            if i % 2 == 0:\n",
    "                dp[i] = dp[i // 2]\n",
    "            else:\n",
    "                dp[i] = dp[i // 2] + dp[i // 2 + 1]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [0, 1]\n",
    "        big = 1\n",
    "        for i in range(2, n+1):\n",
    "            if i % 2 == 0:\n",
    "                dp.append(dp[i//2])\n",
    "            else:\n",
    "                dp.append(dp[i//2]+dp[i//2+1])\n",
    "            big = max(big, dp[i])\n",
    "        return big"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n==0 : return 0\n",
    "        nums = [0]*(n+1)\n",
    "        nums[0] = 0\n",
    "        nums[1] = 1\n",
    "        for i in range(1,n+1):\n",
    "            if 2 * i <= n : nums[2 * i] = nums[i]\n",
    "            if 2 * i +1 <= n : nums[2 * i +1] = nums[i] + nums[i + 1]\n",
    "        nums.sort()\n",
    "        return nums[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n<=1: return n\n",
    "        nums=[0]*(n+1)\n",
    "        nums[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            nums[i]=nums[i//2]+i%2*nums[i//2+1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n <=1:\n",
    "            return n\n",
    "\n",
    "        dp=[0]*(n+1)\n",
    "        dp[0]=0\n",
    "        dp[1]=1\n",
    "        dpmax=1     \n",
    "        for i in range(2,n+1):\n",
    "            if i%2==0:\n",
    "                dp[i]=dp[i//2]\n",
    "            else:\n",
    "                dp[i]=dp[(i-1)//2]+dp[(i+1)//2]\n",
    "            dpmax=max(dpmax,dp[i])\n",
    "        return dpmax\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        f[0], f[1] = 0, 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            t = i // 2\n",
    "            if i % 2 == 0:\n",
    "                f[i] = f[t]\n",
    "            else:\n",
    "                f[i] = f[t] + f[t + 1]\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n<2:\n",
    "            return n\n",
    "        a=[0]*(n+1)\n",
    "        a[1]=1\n",
    "        r=0\n",
    "        for i in range(2,n+1):\n",
    "            if i%2==0:\n",
    "                a[i]=a[i//2]\n",
    "            else:\n",
    "                a[i]=a[i//2]+a[i//2+1]\n",
    "            if a[i]>r:\n",
    "                r=a[i]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n + 1):\n",
    "            if i % 2 == 0:\n",
    "                dp[i] = dp[i // 2]\n",
    "            else:\n",
    "                dp[i] = dp[i//2] + dp[i//2 + 1]\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums = [0] * (n + 1)\n",
    "        nums[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            nums[i] = nums[i // 2] + i % 2 * nums[i // 2 + 1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "        #生成n+1个个数的数组 返回数组的最大值\n",
    "        nums= [0]*110\n",
    "        if  n==0:\n",
    "            return 0\n",
    "        nums[1] = 1\n",
    "        for i in range(1,n//2+1):\n",
    "            if 2*i>=2 and 2*i<=n:\n",
    "                nums[i*2] = nums[i]\n",
    "            if 2*i+1>=2 and 2*i+1<=n:\n",
    "                nums[i*2+1]= nums[i]+nums[i+1]\n",
    "        return max(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGenerated(self, n: int) -> int:\n",
    "            nums=[0]*(n+1)\n",
    "            if n==0:\n",
    "                return 0\n",
    "            nums[1]=1\n",
    "            for i in range(2,n+1):\n",
    "                if i%2==0:\n",
    "                    nums[i]=nums[i//2]\n",
    "                else:\n",
    "                    nums[i]=nums[(i-1)//2]+nums[(i-1)//2+1]\n",
    "            return max(nums)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
